#include "myheader.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <algorithm>
vector<code> codeTable(1);
map<string , int> labelTable;

template <class T> set<T> setUnion(const set<T> &a , const set<T> &b)
{
    vector<T> temp(a.size() + b.size());
    auto it = std::set_union(a.begin() , a.end() , b.begin() , b.end() , temp.begin());
    return set<T>(temp.begin() , it);
}
//Set difference
//return A - B
template <class T> set<T> setDiff(const set<T> &a , const set<T> &b)
{
    vector<T> temp(a.size() + b.size());
    auto it = std::set_difference(a.begin() , a.end() , b.begin() , b.end() , temp.begin());
    return set<T>(temp.begin() , it);
}

template <class T> set<T> setIntr(const set<T> &a , const set<T> &b)
{
    vector<T> temp(a.size() + b.size());
    auto it = std::set_intersection(a.begin() , a.end() , b.begin() , b.end() , temp.begin());
    return set<T>(temp.begin() , it);
}
void phiFunction::rename(int index)
{
    char buf[30];
    sprintf(buf , "%s%d" , (*use.begin()).c_str() , index);
    syms[renameCount++] = buf;
}
int printStatus() {
    cout << "Parsed" << codeTable.size() << "Line of code" << endl;
    for (int i = 0 ; i != codeTable.size() ; ++i)
    {
	cout << "The line " << i << "has:" << endl;
	cout << "Uses: ";
	for (auto x : codeTable[i].use)
	    cout << x << " ";
	cout << endl;
	cout << "Defines:";
	for (auto x : codeTable[i].def)
	    cout << x << " ";
	cout << endl;
	cout << "jumpdes" << codeTable[i].jumpLabel << endl;
    }
}
int CFG_Node::addCode(code &c)
{
    codes.push_back(c);
    return 1;
}
void CFG_Node::addInEdge(CFG_Node *next)
{
    inEdge.push_back(next);
}
void CFG_Node::addOutEdge(CFG_Node *prev)
{
    outEdge.push_back(prev);
    prev->addInEdge(this);
}
CFG_Node::edgeList CFG_Node::gIn()
{
    return inEdge;
}
CFG_Node::edgeList CFG_Node::gOut()
{
    return outEdge;
}
bool CFG_Node::isUse(symInfo sym)
{
    bool flag = false;
    for (auto x : codes)
    {
	if (x.use.find(sym) != x.use.end())
	    flag = true;
    }
    return flag;
}
bool CFG_Node::isDef(symInfo sym)
{
    bool flag = false;
    for (auto x : codes)
    {
	if (x.def.find(sym) != x.def.end())
	    flag = true;
    }
    return flag;
}
void CFG_Node::insertPhiFunction(symInfo sym)
{
    phiFuncs.push_back(phiFunction(sym , inEdge.size()));
}

int CFG_Node::findPhiFunction(symInfo sym)
{
    for (int i = 0 ; i != phiFuncs.size() ; ++i)
	if (phiFuncs[i].symAbout == sym)
	    return i;
    return -1;
}

void CFG_Node::computeDomin()
{
    int domsize = dominSet.size();
    if (inEdge.size() == 0) //The root
    {
	dominSet.erase(dominSet.begin() , dominSet.end());
    }
    else
    {
	set<CFG_Node*> temp = (*inEdge.begin())->dominSet;
	for (CFG_Node* v : inEdge)
	{
	    temp = setIntr(temp , v->dominSet);
	}
	dominSet = temp;
    }
    dominSet.insert(this);
    //If the domin set changed
    if (dominSet.size() != domsize) {
	for (CFG_Node*v : outEdge)
	    v->computeDomin();
    }

    //The immediate domin must be the node
    //which have the most domin node
    CFG_Node* max = *(dominSet.begin());
    for (CFG_Node* x : dominSet)
    {
	if (max->dominSet.size() < x->dominSet.size() && x != this)
	    max = x;
    }
    //If have the previous domin
    if (max != dominImm && dominImm != NULL)
    {
	dominImm->dominTreeChild.remove(this);
    }
    //Insert this pointer to parent
    if (max != dominImm && max != this)
    {
	max->dominTreeChild.push_back(this);
    }
    dominImm = max;
}
void CFG_Node::renameVar(symInfo sym , int baseVarIndex , int &varCount)
{
    //Rename the phi function
    int find = findPhiFunction(sym);
    if (find != -1)
    {
	char temp[20];
	varCount++;
	baseVarIndex = varCount;
	phiFuncs[find].def.clear();
	sprintf(temp , "%s%d" , sym.c_str() , baseVarIndex);
	phiFuncs[find].def.insert(temp);
    }
    for (auto &codeLine : codes)
    {
	if (codeLine.use.find(sym) != codeLine.use.end())
	{
	    //Have a variable used in code
	    int pos = codeLine.codeLine.find("=");
	    if (pos == string::npos)
	    {
		pos = 0;
	    }
	    //Rename the variable
	    int index = codeLine.codeLine.find(sym , pos);
	    while (index != string::npos)
	    {
		char temp[20];
		sprintf(temp , "%d" , baseVarIndex);
		codeLine.codeLine.replace(index , sym.length() , sym + temp);
		codeLine.use.insert(sym + temp);
		index = codeLine.codeLine.find(sym , index + 1);
	    }
	}
	//Rename the define variable
	if (codeLine.def.find(sym) != codeLine.def.end())
	{
	    char temp[20];
	    varCount++;
	    baseVarIndex = varCount;
	    sprintf(temp , "%d" , baseVarIndex);
	    int index = codeLine.codeLine.find(sym);
	    if (index != string::npos)
	    {
		codeLine.codeLine.replace(index , sym.length() , sym + temp);
		codeLine.def.insert(sym + temp);
	    }
	}
    }
    //TODO:Add the rename the phi function
    for (auto x : outEdge)
    {
	if (x != this)
	{
	    int find = x->findPhiFunction(sym);
	    if (find != -1)
	    {
		x->phiFuncs[find].rename(baseVarIndex);
	    }
	}
    }
    //rename childs
    for (auto x : dominTreeChild)
	x->renameVar(sym , baseVarIndex , varCount);
}

void CFG_Node::computeDF()
{
    for (CFG_Node* v : outEdge)
    {
	if (v->dominImm != this)
	    DF.insert(v);
    }
    for (CFG_Node *v : dominTreeChild)
    {
	if (v != this)
	    v->computeDF();
	for (CFG_Node *p : v->DF)
	{
	    if (p->dominImm != this)
	    {
		DF.insert(p);
	    }
	}
    }
}

CFG::CFG()
{
}

void CFG::addNode(CFG_Node T)
{
    nodeVec.push_back(T);
    nodeVec.back().CFGid = nodeVec.size() - 1;
    for (code c : T.codes)
    {
	for (symInfo var : c.def)
	    symTable.insert(var);
	for (symInfo var : c.use)
	    symTable.insert(var);
    }
}

void CFG::linkNode(int start , int end)
{
    nodeVec[start].addOutEdge(&nodeVec[end]);
}

void CFG::computeDomin()
{
    set<CFG_Node*> allSet;
    for (auto &x : nodeVec)
	allSet.insert(&x);
    for (auto &x : nodeVec)
	x.dominSet = allSet;
    nodeVec[root()].computeDomin();
}

void CFG::computeDF()
{
    computeDomin();
    nodeVec[root()].computeDF();
}

int CFG::root()
{
    static int rootIndex = -1;
    if (rootIndex == -1)
    {
	int i;
	for (int i = 0 ; i != nodeVec.size() ; ++i)
	    if (nodeVec[i].gIn().size() == 0 && nodeVec[i].gOut().size() != 0)
	    {
		rootIndex = i;
		return i;
	    }
    }
    else
	return rootIndex;
}

void CFG::ssa()
{
    computeDF();
    map<symInfo , set<CFG_Node*> > symDef;

    for (symInfo sym : symTable)
    {
	symDef[sym] = set<CFG_Node*>();
	for (int i = 0 ; i != nodeVec.size() ; ++i)
	    if (nodeVec[i].isDef(sym))
		symDef[sym].insert(&nodeVec[i]);

	while (symDef[sym].size() != 0)
	{
	    CFG_Node *temp = *symDef[sym].begin();
	    symDef[sym].erase(temp);
	    for (auto ptr : temp->DF)
		if (ptr->findPhiFunction(sym) == -1)
		{
		    if (!ptr->isDef(sym))
			symDef[sym].insert(ptr);
		    ptr->insertPhiFunction(sym);
		}
	}
	//Rename the variable
	int varCount = 0;
	nodeVec[root()].renameVar(sym , 0 , varCount);
    }
}

void CFG::printCFG(ostream &os)
{
    os << "digraph G {" << endl;
    os << "compund = true;" << endl;
    for (CFG_Node &v : nodeVec)
    {
	os << "n" << v.CFGid << " [label=\"";
	//Phi function
	for (phiFunction &phi : v.phiFuncs)
	{
	    os << *phi.def.begin() << "=Phi(";
	    os << phi.syms[0];
	    for (int i = 1 ; i != phi.syms.size() ; ++i)
		os << "," << phi.syms[i];
	    os << ")\\n";
	}
	if (v.codes.size() > 0)
	{
	    for (int i = 0 ; i < v.codes.size() - 1 ; ++i)
		os << v.codes[i].codeLine << "\\n";
	    os << v.codes.back().codeLine;
	}
	os << "\" , shape=box]" << endl;
    }

    for (CFG_Node &v : nodeVec)
    {
	for (CFG_Node *child : v.gOut())
	    os << "n" << v.CFGid << "->" << "n" << child->CFGid << ";" << endl;
    }
    os << "}" << endl;
}

void generateCFG()
{
}
